package com.bm;

/**
 * Description: BM53 缺失的第一个正整数
 *
 * @author weiruibai.vendor
 * Date: 2022/9/26 10:03
 */
public class BM53 {

    public static void main(String[] args) {
      /*  System.out.println(1 << 0);
        System.out.println(1 << 1);
        System.out.println(1 << 2);
*/
        BM53 bm53 = new BM53();
        int[] nums = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
                10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
                20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
                30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
                40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
                50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
                60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
                70
        };
        nums = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8,
                10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
                20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
                30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
                40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
                50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
                60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
                70
        };
        //nums = new int[]{1, 1};
        //nums = new int[]{2, 2};
        //nums = new int[]{2, 1};
        //nums = new int[]{2};
        // nums = new int[]{3, 3, 1, 4, 0};
        System.out.println(bm53.minNumberDisappeared_v3(nums));
    }


    ////////////////////////////////////////////////
    private int minNumberDisappeared_v3(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        int L = 0;
        int R = nums.length;
        while (L < R) {
            int val = nums[L];
            if (val < L + 1) {
                swap(nums, L, --R);
            } else if (val == L + 1) {
                L++;
            } else if (val > R || nums[L] == nums[R - 1]) {
                // 如果两位要交换的值相等，那么也需要R--
                swap(nums, L, --R);
            } else if (val <= R && val == nums[val - 1]) {
                // 下标L对应的值和val 该值应该对应的下标val-1，下标val-1对应的值如果相等，说明有重复，R需要减1
                swap(nums, L, --R);
            } else {
                swap(nums, L, val - 1);
            }
        }
        return R + 1;
    }


    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}


